1. Field of Invention
The present invention relates to a method of buffer management and task scheduling. More particularly, the present invention relates to a method of buffer management and task scheduling for two-dimensional data transforming.
2. Description of Related Art
Two-dimensional Discrete Fourier Transforms, such as Discrete Cosine Transform (DCT), are widely used in image processing, digital signal processing, digital communications, etc. Due to its intrinsic properties, two-dimensional transform operation requires significant amount of memory to store data. One good example is a two-dimensional DCT (2D-DCT) operated on a two-dimensional image. As illustrated in FIG. 1, an image 10 is scanned line-by-line from the left-top corner to the right-bottom corner. In order to perform 2D-DCT with 6×6 block size 12, at least five lines of data 16 have to be stored. Furthermore, new input data (not shown) keeps coming in while old data 14 are being processed. Since the input data follow a line-by-line pattern and the old data 14 are processed in a block-by-block pattern, there is a conflict in memory space.
Traditionally, there are two solutions to solve this problem. The first solution is to use two six-line buffers, one for reading out data and the other for writing data in, and then swapping the buffers every six lines. However, this requires double the memory space than required in theory. The second solution is to process the 2D-DCT very quickly and to clean out the memory space before the read-write conflict occurs. Though, this causes significant processing bursts while receiving the “last line” 18 of the 6×6 blocks 12. It does not only require very extensive computations for such processing bursts, but also waste the computing resources while staying idle and waiting for all necessary data to be processed.
The invention provides a new solution to the problem stated above. The invention uses the minimum space required in theory and distributes the process loading evenly in time domain. It eliminates the trade-off between memory size and computing power, which has been recognized as a serious dilemma in 2D Discrete Fourier Transforms. The invention also presents a practical implementation of these presented ideas which is very simple and, therefore, consumes much less power than traditional designs do.